package com.xmg.dataStructure.tree.threadedbinarytree;

/**
 * 线索化二叉树
 */
public class ThreadedBinaryTreeDemo {
    public static void main(String[] args) {
        HeroNode root = new HeroNode(1,"tom");
        HeroNode node2 = new HeroNode(2,"kate");
        HeroNode node3 = new HeroNode(3,"stack");
        HeroNode node4 = new HeroNode(4,"james");
        HeroNode node5 = new HeroNode(5,"kobe");
        HeroNode node6 = new HeroNode(6,"sole");
        root.setLeft(node2);
        root.setRight(node3);
        node2.setLeft(node4);
        node2.setRight(node5);
        node3.setLeft(node6);
        node2.setParent(root);
        node3.setParent(root);
        node4.setParent(node2);
        node5.setParent(node2);
        node6.setParent(node3);
        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.setRoot(root);
//        System.out.println("常规前序遍历");
//        tree.preOrder();
//        System.out.println("后序常规遍历");
//        tree.postOrder();
//        System.out.println("前序线索化");
//        tree.preThreadedNodes();
//        System.out.println("中序线索化");
//        tree.infixThreadedNodes();
        System.out.println("后序线索化");
        tree.postThreadedNodes();

//        System.out.println(node4.getLeftType());
//        System.out.println(node4.getRight());

//        tree.infixThreadedList();
//        tree.preThreadedList();
        tree.postThreadedList();
    }
}



class ThreadedBinaryTree{
    private HeroNode root;
    //递归线索化时，保存前一个节点
    private HeroNode pre = null;

    public void setRoot(HeroNode root) {
        this.root = root;
    }

    public void preOrder(){
        if(this.root!=null){
            this.root.preOrder();
        }
    }
    public void infixOrder(){
        if(this.root!=null){
            this.root.infixOrder();
        }
    }
    public void postOrder(){
        if(this.root!=null){
            this.root.postOrder();
        }
    }
    public void infixThreadedNodes(){
        this.infixThreadedNodes(root);
    }

    //中序遍历线索化之后的二叉树
    public void infixThreadedList(){
        HeroNode node = root;
        while (node!=null){
            while (node.getLeftType() == 0){
                node = node.getLeft();
            }
            System.out.println(node);
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }

    //前序遍历线索化之后的二叉树
    public void preThreadedList(){
        HeroNode node = root;
        while (node!=null){
            System.out.println(node);
            while (node.getLeftType() == 0){
                node = node.getLeft();
                System.out.println(node);
            }
            while (node.getRightType() == 1){
                node = node.getRight();
                System.out.println(node);
            }
            node = node.getRight();
        }
    }

    //后序遍历线索化之后的二叉树
    public void postThreadedList(){
        HeroNode node = root;
        while (node!=null && node.getLeftType() == 0){
            node = node.getLeft();
        }
        HeroNode preNode = null;
        while (node!=null){
            if (node.getRightType()==1){
                System.out.println(node);
                preNode = node;
                node = node.getRight();
            }else{
                if(preNode == node.getRight()){
                    System.out.println(node);
                    if(node==root){
                        return;
                    }
                    preNode = node;
                    node = node.getParent();
                }else{
                    node = node.getRight();
                    while (node!=null && node.getLeftType()==0){
                        node = node.getLeft();
                    }
                }
            }
        }
    }

    public void infixThreadedNodes(HeroNode node){
        if (node==null){
            return;
        }

        //线索化左子树
        infixThreadedNodes(node.getLeft());
        //线索化当前结点
        //处理当前结点的前驱结点
        if(node.getLeft() == null){
            node.setLeft(pre);
            node.setLeftType(1);//结点左指针为前驱结点
        }

        //处理后继结点
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        //！！！处理一个节点后，让当前结点是下一个节点的前驱结点
        pre = node;
        //线索化右子树
        infixThreadedNodes(node.getRight());
    }

    public void preThreadedNodes(){
        this.preThreadedNodes(root);
    }

    public void preThreadedNodes(HeroNode node){
        if (node==null){
            return;
        }
        //线索化当前结点
        if(node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
        //线索化左节点
        if(node.getLeftType()==0) {
            preThreadedNodes(node.getLeft());
        }
        //线索化右节点
        if(node.getRightType()==0) {
            preThreadedNodes(node.getRight());
        }
    }

    public void postThreadedNodes(){
        this.postThreadedNodes(root);
    }

    public void postThreadedNodes(HeroNode node){
        if (node==null){
            return;
        }

        //线索化左节点
//        if(node.getLeftType()==0) {
        postThreadedNodes(node.getLeft());
//        }
        //线索化右节点
//        if(node.getRightType()==0) {
        postThreadedNodes(node.getRight());
//        }
        //线索化当前结点
        if(node.getLeft()==null){
            node.setLeft(pre);
            node.setLeftType(1);
        }
        if(pre != null && pre.getRight() == null){
            pre.setRight(node);
            pre.setRightType(1);
        }
        pre = node;
    }
}

class HeroNode{
    private int no;
    private String name;

    private HeroNode left;
    private HeroNode right;
    private HeroNode parent; //后续线索化时使用
    //节点属性 0 左右子树节点  1 前驱 后继节点
    private int leftType;
    private int rightType;

    public int getLeftType() {
        return leftType;
    }

    public void setLeftType(int leftType) {
        this.leftType = leftType;
    }

    public int getRightType() {
        return rightType;
    }

    public void setRightType(int rightType) {
        this.rightType = rightType;
    }

    public HeroNode(int no, String name) {
        this.no = no;
        this.name = name;
    }

    public int getNo() {
        return no;
    }

    public void setNo(int no) {
        this.no = no;
    }

    public String getName() {
        return name;
    }

    public void setName(String name) {
        this.name = name;
    }

    public HeroNode getLeft() {
        return left;
    }

    public void setLeft(HeroNode left) {
        this.left = left;
    }

    public HeroNode getRight() {
        return right;
    }

    public void setRight(HeroNode right) {
        this.right = right;
    }

    public HeroNode getParent() {
        return parent;
    }

    public void setParent(HeroNode parent) {
        this.parent = parent;
    }

    @Override
    public String toString() {
        return "HeroNode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

    public void preOrder(){
        System.out.println(this.toString());
        if(this.left!=null){
            this.left.preOrder();
        }
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    public void infixOrder(){
        if(this.left!=null){
            this.left.preOrder();
        }
        System.out.println(this.toString());
        if(this.right!=null){
            this.right.preOrder();
        }
    }

    public void postOrder(){
        if(this.left!=null){
            this.left.postOrder();
        }
        if(this.right!=null){
            this.right.postOrder();
        }
        System.out.println(this.toString());

    }
}
